 <!DOCTYPE html>

 <html>

<head>
    <meta charset="utf-8">
    <title>
        数组使用
    </title>
    <style type="text/css">
        .radio-list {
            font-size: 16px;
            text-align: left;
        }

        .radio-list input {
            width: 16px;
            height: 16px;
            cursor: pointer;
        }

        .panel {
            display: none;
        }

        .un-detail,
        .sort-detail,
        .random-detail {
            display: none;
            margin: 20px 0px;
        }
    </style>
    <link rel="icon" href="favicon.ico" type="image/x-icon"/>
    <link rel="shortcut icon" href="favicon.ico" type="image/x-icon"/>

</head>

<body>
<h3>数组用法</h3>
<div class='btn-list' id="btnCont">
    <button id="uniqueBtn" class="radius-btn">数组去重</button>
    <button id="sortBtn" class="radius-btn">数组排序</button>
    <button id="randomBtn" class="radius-btn">随机数组</button>
    <button id="twoTree" class="radius-btn">二叉树</button>
</div>

<div id="uniquePanel" class="panel">
    <p>数组去重</p>
    <p>原始数组： [4, 2, 5, 5,5, 8,8, 12, 43, 7, 2]</p>
    <div class="radio-list">
        <input type="radio" name="unique" data-id="r1"/>
        <label>遍历数组法</label>
        <input type="radio" name="unique" data-id="r2"/>
        <label>对象键值对法</label>
        <input type="radio" name="unique" data-id="r3"/>
        <label>数组下标判断法</label>
        <input type="radio" name="unique" data-id="r4"/>
        <label>排序后相邻去除法</label>
        <input type="radio" name="unique" data-id="r5"/>
        <label>优化遍历数组法</label>
    </div>

    <div class="unique-details" id="unDetail">
        <div class="un-detail" id="r1">
            <strong>结果：</strong>
            <p id='r1-res'></p>
            <p>检测浏览器是否支持ECMA5</p>
            <pre class='brush: javascript'>
                // 判断浏览器是否支持indexOf ，indexOf 为ecmaScript5新方法 IE8以下（包括IE8， IE8只支持部分ecma5）不支持
                if (!Array.prototype.indexOf){
                  // 新增indexOf方法
                  Array.prototype.indexOf = function(item){
                    var result = -1, a_item = null;
                    if (this.length == 0){
                      return result;
                    }
                    for(var i = 0, len = this.length; i < len; i++){
                      a_item = this[i];
                      if (a_item === item){
                        result = i;
                        break;
                      }
                    }
                    return result;
                  }
                }
              </pre>
            <p>普通遍历数组法：</p>
            <pre class='brush: javascript'>
                // 最简单数组去重法
                function unique1(array){
                  var n = []; //一个新的临时数组
                  //遍历当前数组
                  for(var i = 0; i < array.length; i++){
                    //如果当前数组的第i已经保存进了临时数组，那么跳过，
                    //否则把当前项push到临时数组里面
                    if (n.indexOf(array[i]) == -1) n.push(array[i]);
                  }
                  return n;
                }
              </pre>
        </div>
        <div class="un-detail" id="r2">
            <strong>结果：</strong>
            <p id="r2-res"></p>
            <p>对象键值对法：</p>
            <pre class='brush: javascript'>
                // 速度最快， 占空间最多（空间换时间）
                function unique2(array){
                  var n = {}, r = [], len = array.length, val, type;
                    for (var i = 0; i < array.length; i++) {
                        val = array[i];
                        type = typeof val;
                        if (!n[val]) {
                            n[val] = [type];
                            r.push(val);
                        } else if (n[val].indexOf(type) < 0) {
                            n[val].push(type);
                            r.push(val);
                        }
                    }
                    return r;
                }
              </pre>
        </div>
        <div class="un-detail" id="r3">
            <strong>结果：</strong>
            <p id="r3-res"></p>
            <p>数组下标判断法</p>
            <pre class="brush:javascript">
                function unique3(array){
                <!-- var n = [array[0]]; //结果数组 -->
                  var n = [];
                  //从第二项开始遍历
                <!-- for(var i = 1; i < array.length; i++) { -->
                  for(var i = 0; i < array.length; i++) {
                    //如果当前数组的第i项在当前数组中第一次出现的位置不是i，
                    //那么表示第i项是重复的，忽略掉。否则存入结果数组
                    if (array.indexOf(array[i]) == i) n.push(array[i]);
                  }
                  return n;
                }
              </pre>
        </div>
        <div class="un-detail" id="r4">
            <strong>结果：</strong>
            <p id="r4-res"></p>
            <p>排序后相邻去除法</p>
            <pre class="brush:javascript">
                // 将相同的值相邻，然后去除
                function unique4(array){
                  array.sort();
                  var re=[array[0]];
                  for(var i = 1; i < array.length; i++){
                    if( array[i] !== re[re.length-1])
                    {
                      re.push(array[i]);
                    }
                  }
                  return re;
                }
              </pre>
        </div>
        <div class="un-detail" id="r5">
            <strong>结果：</strong>
            <p id="r5-res"></p>
            <p>优化遍历数组法:</p>
            <pre class="brush:javascript">
                // 思路：获取没重复的最右一值放入新数组
                function unique5(array){
                  var r = [];
                  for(var i = 0, l = array.length; i < l; i++) {
                    for(var j = i + 1; j < l; j++)
                      if (array[i] === array[j]) j = ++i;
                    r.push(array[i]);
                  }
                  return r;
                }
              </pre>
        </div>
    </div>

</div>

<div id="sortPanel" class="panel">
    <p>原始数组： [5,6,3,4,9,7,8,12,10,11,2,1]</p>
    <div class="radio-list">
        <input type="radio" name="sort" data-id="s1"/>
        <label>插入排序</label>
        <input type="radio" name="sort" data-id="s2"/>
        <label>二分插入排序</label>
        <input type="radio" name="sort" data-id="s3"/>
        <label>希尔排序</label>
        <input type="radio" name="sort" data-id="s4"/>
        <label>冒泡排序</label>
        <input type="radio" name="sort" data-id="s5"/>
        <label>改进冒泡排序</label>
        <input type="radio" name="sort" data-id="s6"/>
        <label>快速排序</label>
        <input type="radio" name="sort" data-id="s7"/>
        <label>选择排序</label>
        <input type="radio" name="sort" data-id="s8"/>
        <label>堆排序</label>
        <input type="radio" name="sort" data-id="s9"/>
        <label>归并排序</label>
        <input type="radio" name="sort" data-id="s10"/>
        <label>计数排序</label>
        <input type="radio" name="sort" data-id="s11"/>
        <label>基数排序</label>
        <input type="radio" name="sort" data-id="s12"/>
        <label>桶排序</label>

    </div>

    <div class="sort-details" id="sortDetail">
        <div class="sort-detail" id="s1">
            <strong>结果：</strong>
            <p id="s1-res"></p>
            <p>原理图：</p>
            <img title="插入排序动画原理图" alt="插入排序动画原理图" src="./sort/Insertion.gif"/>
            <p>插入排序算法</p>
            <pre class="brush:javascript">
                // 插入排序 从下标1开始每增1项排序一次，越往后遍历次数越多
                function sort1(array) {
                  var len = array.length,
                      i, j, tmp, result;

                  // 设置数组副本
                  result = array.slice(0);
                  for(i=1; i < len; i++){
                    tmp = result[i];
                    j = i - 1;
                    while(j>=0 && tmp < result[j]){
                      result[j+1] = result[j];
                      j--;
                    }
                    result[j+1] = tmp;
                  }
                  return result;
                }
              </pre>
        </div>
        <div class="sort-detail" id="s2">
            <strong>结果：</strong>
            <p id="s2-res"></p>
            <p>原理图：</p>
            <p>二分插入排序</p>
            <pre class="brush:javascript">
                // 先在有序区通过二分查找的方法找到移动元素的起始位置，然后通过这个起始位置将后面所有的元素后移
                function sort2(array) {
                  var len = array.length,
                      i, j, tmp, low, high, mid, result;
                  // 赋予数组副本
                  result = array.slice(0);
                  for(i = 1; i < len; i++){
                    tmp = result[i];
                    low = 0;
                    high = i - 1;
                    while(low <= high){
                      mid = parseInt((low + high)/2, 10);
                      if(tmp < result[mid]) high = mid - 1;
                      else low = mid + 1;
                    }
                    for(j = i - 1; j >= high+1; j--){
                      result[j+1] = result[j];
                    }
                    result[j+1] = tmp;
                  }
                  return result;
                }
              </pre>
        </div>
        <div class="sort-detail" id="s3">
            <strong>结果：</strong>
            <p id="s3-res"></p>
            <p>原理图：</p>
            <p>希尔排序</p>
            <pre class="brush:javascript">
                // 希尔排序：先将整个待排序记录序列分割成若干个子序列，在在序列内分别进行直接插入排序，待整个序列基本有序时，再对全体记录进行一次直接插入排序
                function sort3(array){
                  var len = array.length, gap = parseInt(len/2),
                      i, j, tmp, result;
                  // 复制数组
                  result = array.slice(0);
                  while(gap > 0){
                    for(i = gap; i < len; i++){
                      tmp = result[i];
                      j = i - gap;
                      while(j>=0 && tmp < result[j]){
                        result[j + gap] = result[j];
                        j = j - gap;
                      }
                      result[j + gap] = tmp;
                    }
                    gap = parseInt(gap/2);
                  }
                  return result;
                }
              </pre>
        </div>
        <div class="sort-detail" id="s4">
            <strong>结果：</strong>
            <p id="s4-res"></p>
            <p>原理图：</p>
            <img title="冒泡排序动画原理图" alt="冒泡排序动画原理图" src="./sort/bubble.gif"/>
            <p>冒泡排序</p>
            <pre class="brush:javascript">
                // 冒泡排序 每次将最小元素推至最前
                function sort4(array) {
                  var len = array.length,
                  i, j, tmp, result;
                  result = array.slice(0);
                  for (i = 0; i < len; i++) {
                    for (j = len - 1; j > i; j--) {
                      if (result[j] < result[j - 1]) {
                        tmp = result[j - 1];
                        result[j - 1] = result[j];
                        result[j] = tmp;
                      }
                    }
                  }
                  return result;
                }
              </pre>
        </div>
        <div class="sort-detail" id="s5">
            <strong>结果：</strong>
            <p id="s5-res"></p>
            <p>原理图：</p>
            <img title="冒泡排序动画原理图" alt="冒泡排序动画原理图" src="./sort/bubble.gif"/>
            <p>改进冒泡排序</p>
            <pre class="brush:javascript">
                // 如果在某次的排序中没有出现交换的情况，那么说明在无序的元素现在已经是有序了，就可以直接返回了。
                function sort5(array) {
                  var len = array.length,
                  i, j, tmp, exchange, result;

                  result = array.slice(0);
                  for (i = 0; i < len; i++) {
                    exchange = 0;
                    for (j = len - 1; j > i; j--) {
                      if (result[j] < result[j - 1]) {
                        tmp = result[j];
                        result[j] = result[j - 1];
                        result[j - 1] = tmp;
                        exchange = 1;
                      }
                    }
                    if (!exchange) return result;
                  }
                  return result;
                }
              </pre>
        </div>
        <div class="sort-detail" id="s6">
            <strong>结果：</strong>
            <p id="s6-res"></p>
            <p>原理图：</p>
            <img title="快速排序动画原理图" alt="快速排序动画原理图" src="./sort/quick.gif"/>
            <p>快速排序</p>
            <pre class="brush:javascript">
                //（1）在数据集之中，选择一个元素作为"基准"（pivot）。
                //（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
                //（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
                function sort6(array) {
                  var tmp_array = array.slice(0), result,
                  quickSort = function(arr) {
                　　if (arr.length <= 1) { return arr; }
                　　var pivotIndex = Math.floor(arr.length / 2);
                　　var pivot = arr.splice(pivotIndex, 1)[0];
                　　var left = [];
                　　var right = [];
                　　for (var i = 0; i < arr.length; i++){
                　　　　if (arr[i] < pivot) {
                　　　　　　left.push(arr[i]);
                　　　　} else {
                　　　　　　right.push(arr[i]);
                　　　　}
                　　}
                　　return quickSort(left).concat([pivot], quickSort(right));
                  };
                  result = quickSort(tmp_array);
                  return result;
                }
              </pre>
        </div>
        <div class="sort-detail" id="s7">
            <strong>结果：</strong>
            <p id="s7-res"></p>
            <p>原理图：</p>
            <img title="选择排序动画原理图" alt="选择排序动画原理图" src="./sort/selection.gif"/>
            <p>选择排序</p>
            <pre class="brush:javascript">
                // 在无序区中选出最小的元素，然后将它和无序区的第一个元素交换位置。
                // 原理跟冒泡排序一样，算是冒泡的衍生版本
                function sort7(array) {
                  var len = array.length,
                  i, j, k, tmp, result;

                  result = array.slice(0);
                  for (i = 0; i < len; i++) {
                    k = i;
                    for (j = i + 1; j < len; j++) {
                      if (result[j] < result[k]) k = j;
                    }
                    if (k != i) {
                      tmp = result[k];
                      result[k] = result[i];
                      result[i] = tmp;
                    }
                  }
                  return result;
                }
              </pre>
        </div>
        <div class="sort-detail" id="s8">
            <strong>结果：</strong>
            <p id="s8-res"></p>
            <p>原理图：</p>
            <img title="堆排序动画原理图" alt="堆排序动画原理图" src="./sort/heap.gif"/>
            <div>
                <strong>1.调整二叉树，形成大根堆(子节点都比父节点小)。</strong>
            </div>
            <div>
                <strong>2.交换堆第一元素跟最后元素位置，最后元素弹出堆。然后继续回到1，调整堆。</strong>
            </div>
            <div>
                <strong>3.重复2， 当所有节点弹出堆后；弹出的节点值就是有序的了。</strong>
            </div>
            <p>堆排序</p>
            <pre class="brush:javascript">
                // 1) 初始堆：将原始数组调整成大根堆的方法——筛选算法:子节点都比父节点小
                // 2) 堆排序： 每次将堆顶元素与数组最后面的且没有被置换的元素互换。
                function sort8(array) {
                  var result = array.slice(0);

                  function swap(array, i, j) {
                    var temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                  }

                  function maxHeapify(array, index, heapSize) {
                    var iMax, iLeft, iRight;
                    while (true) {
                      iMax = index;
                      iLeft = 2 * index + 1;
                      iRight = 2 * (index + 1);

                      if (iLeft < heapSize && array[index] < array[iLeft]) {
                        iMax = iLeft;
                      }

                      if (iRight < heapSize && array[iMax] < array[iRight]) {
                        iMax = iRight;
                      }

                      if (iMax != index) {
                        swap(array, iMax, index);
                        index = iMax;
                      } else {
                        break;
                      }
                    }
                  }

                  function buildMaxHeap(array) {
                    var i, iParent = Math.floor(array.length / 2) - 1;

                    for (i = iParent; i >= 0; i--) {
                      maxHeapify(array, i, array.length);
                    }
                  }

                  function sort(array) {
                    buildMaxHeap(array);

                    for (var i = array.length - 1; i > 0; i--) {
                      swap(array, 0, i);
                      maxHeapify(array, 0, i);
                    }
                    return array;
                  }

                  return sort(result);
                }
              </pre>
        </div>
        <div class="sort-detail" id="s9">
            <strong>结果：</strong>
            <p id="s9-res"></p>
            <p>原理图：</p>
            <img title="归并排序动画原理图" alt="归并排序动画原理图" src="./sort/merge.gif"/>
            <p>归并排序</p>
            <pre class="brush:javascript">

                function sort9(array) {
                  var result = array.slice(0);

                  // 递归调用合并函数
                  function sort(array) {
                    var length = array.length,
                    mid = Math.floor(length * 0.5),
                    left = array.slice(0, mid),
                    right = array.slice(mid, length);

                    if (length === 1) {
                      return array;
                    }
                    return merge(sort(left), sort(right));
                  }

                  // 合并 两有序的数组
                  function merge(left, right) {
                    var result = [];

                    while (left.length || right.length) {

                      if (left.length && right.length) {

                        if (left[0] < right[0]) {
                          result.push(left.shift());
                        } else {
                          result.push(right.shift());
                        }

                      } else if (left.length) {
                        result.push(left.shift());
                      } else {
                        result.push(right.shift());
                      }
                    }
                    return result;
                  }

                  return sort(result);
                }
              </pre>
        </div>

        <div class="sort-detail" id="s10">
            <strong>结果：</strong>
            <p id="s9-res"></p>
            <p>原理图：</p>
            <img title="计数排序动画原理图" alt="计数排序动画原理图" src="./sort/counting.gif"/>
            <p>计数排序</p>
            <pre class="brush:javascript">

                  function countingSort(arr, maxValue) {
                    var bucket = new Array(maxValue+1),
                        sortedIndex = 0;
                        arrLen = arr.length,
                        bucketLen = maxValue + 1;

                    for (var i = 0; i < arrLen; i++) {
                        if (!bucket[arr[i]]) {
                            bucket[arr[i]] = 0;
                        }
                        bucket[arr[i]]++;
                    }

                    for (var j = 0; j < bucketLen; j++) {
                        while(bucket[j] > 0) {
                            arr[sortedIndex++] = j;
                            bucket[j]--;
                        }
                    }

                    return arr;
                }
            </pre>
        </div>
        <div class="sort-detail" id="s11">
            <strong>结果：</strong>
            <p id="s9-res"></p>
            <p>原理图：</p>
            <img title="基数排序动画原理图" alt="基数排序动画原理图" src="./sort/radix.gif"/>
            <p>基数排序</p>
            <pre class="brush:javascript">

                  var counter = [];
                  function radixSort(arr, maxDigit) {
                      var mod = 10;
                      var dev = 1;
                      for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
                          for(var j = 0; j < arr.length; j++) {
                              var bucket = parseInt((arr[j] % mod) / dev);
                              if(counter[bucket]==null) {
                                  counter[bucket] = [];
                              }
                              counter[bucket].push(arr[j]);
                          }
                          var pos = 0;
                          for(var j = 0; j < counter.length; j++) {
                              var value = null;
                              if(counter[j]!=null) {
                                  while ((value = counter[j].shift()) != null) {
                                        arr[pos++] = value;
                                  }
                            }
                          }
                      }
                      return arr;
                  }
            </pre>
        </div>
        <div class="sort-detail" id="s12">
            <strong>结果：</strong>
            <p id="s9-res"></p>
            <p>原理图：</p>

            <p>桶排序</p>
            <pre class="brush:javascript">
                  function bucketSort(arr, bucketSize) {
                    if (arr.length === 0) {
                      return arr;
                    }

                    var i;
                    var minValue = arr[0];
                    var maxValue = arr[0];
                    for (i = 1; i < arr.length; i++) {
                      if (arr[i] < minValue) {
                          minValue = arr[i];                //输入数据的最小值
                      } else if (arr[i] > maxValue) {
                          maxValue = arr[i];                //输入数据的最大值
                      }
                    }

                    //桶的初始化
                    var DEFAULT_BUCKET_SIZE = 5;            //设置桶的默认数量为5
                    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
                    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
                    var buckets = new Array(bucketCount);
                    for (i = 0; i < buckets.length; i++) {
                        buckets[i] = [];
                    }

                    //利用映射函数将数据分配到各个桶中
                    for (i = 0; i < arr.length; i++) {
                        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
                    }

                    arr.length = 0;
                    for (i = 0; i < buckets.length; i++) {
                        insertionSort(buckets[i]);                      //对每个桶进行排序，这里使用了插入排序
                        for (var j = 0; j < buckets[i].length; j++) {
                            arr.push(buckets[i][j]);
                        }
                    }

                    return arr;
                }
            </pre>
        </div>
    </div>

</div>

<div id="randomPanel" class="panel">
    <p>显示随机数组</p>
    <p>原始数组： [8,2, 3, 55, 12, 20, 16, 18, 15, 20, 11, 7]</p>
    <div class="radio-list">
        <input type="radio" name="random" data-id="ran1"/>
        <label>从数组中随机获取N个不重复的值</label>
        <input type="radio" name="random" data-id="ran2"/>
        <label>打乱数组顺序，要求数组中的每个元素都不能停留在原来的位置</label>
        <input type="radio" name="random" data-id="ran3"/>
        <label>从指定范围内，随机获取N个值的数组</label>
    </div>

    <div class="random-details" id="randomDetail">
        <div class="random-detail" id="ran1">
            <strong>结果：</strong>
            <p id="ran1-res"></p>

            <p>对应代码：</p>
            <pre class="brush:javascript">
                // 随机从数组中获取 N个不重复的值, 默认从数组取一个值
                function ran1(array, n){
                  var _result = [], _index = 0, _arrayTemp;
                  // 防止原数组被改变
                  _arryTemp = array.slice(0);
                  if (array == null || array.length == 0 || array.length < n){
                    return _result;
                  }
                  // 随机获取一个值
                  if (n == null){
                    _index = Math.floor(Math.random() * array.length);
                    _result.push(array[_index]);
                  }else{
                    // 随机获取N个值
                    for (var i = 0; i < n; i++){
                      _index = Math.floor(Math.random() * _arrayTemp.length);
                      _result.push(_arrayTemp[_index]);
                      // 删除该元素
                      _arrayTemp.splice(_index, 1);
                    }
                  }
                  return _result;
                }
              </pre>
        </div>

        <div class="random-detail" id="ran2">
            <strong>结果：</strong>
            <p id="ran2-res"></p>

            <p>对应代码：</p>
            <pre class="brush:javascript">
                // 随机打乱数组，使数组内元素与原来位置完全不同
                function ran2(array){
                  var array_tmp = [], i , j, len, new_a = [], a_obj;

                  // 添加数组原位置标志位
                  for (i = 0, len = array.length; i < len; i++) {
                    a_obj = {
                      'key': i,
                      'val': array[i]
                    };
                    array_tmp.push(a_obj);
                  }

                  for (i = 0, len = array.length; i < len; i++) {
                    j = ranCount(array_tmp.length);
                    // 如下标位置与原值重复，重新随机
                    while ( i === array_tmp[j].key ) {
                      j = ranCount(array_tmp.length);
                    }
                    new_a.push( array_tmp[j].val );
                    // 删除数组
                    array_tmp.splice(j,1);
                  }

                  // 获得给定数字的随机数, 出错返回-1
                  function ranCount(n){
                    var result = parseInt(n, 10);
                    if ( isNaN(result) ) {
                      result = -1;
                    }
                    result = Math.floor(Math.random() * result)
                    return result;
                  }

                  return new_a;
                  }
              </pre>
        </div>

        <div class="random-detail" id="ran3">
            <strong>结果：</strong>
            <p id="ran3-res"></p>

            <p>对应代码：</p>
            <pre class="brush:javascript">
                // 从指定范围内(暂定为100以内)，随机获取N（暂定为10）个值的数组
                function ran3(){
                  var result = [], SCOPE_NO = 100, COUNT = 10;

                  result = getRandomNo(SCOPE_NO, COUNT);
                  function getRandomNo(scope_no, count){
                    var i, s_n, ran_n, _result = [];

                    s_n = parseInt(scope_no, 10);
                    for (i = 0; i < count; i++) {
                      ran_n = Math.floor(Math.random() * s_n);
                      _result.push(ran_n);
                    }
                    return _result;
                  }

                  return result;
                }
              </pre>
        </div>
    </div>
</div>
<div id="twoTreePanel" class="panel">
    <div id="twoTreeDetail">
        <div>
            <div class="radio-list">
                <input type="radio" name="random" data-id="ran4"/>
                <label>ES6</label>
                <input type="radio" name="random" data-id="ran5"/>
                <label>ES5</label>
            </div>
            <p>对应代码：</p>
            <div class="random-detail" id="ran4">
                <pre class="brush:javascript">
// 二叉树是一种从上往下的树状结构的数据结构，从根节点开始每个节点最多有两个子节点，
//
// 分别是：左边的为左子节点，右边的为右子节点。
//
// 排序二叉树是有顺序的，且没有重复元素的二叉树。顺序为：
//
// 对每个节点而言：
//
// 1）如果左子树不为空，则左子树上的所有节点都小于该节点；
//
// 2）如果右子树不为空，则右子树上的所有节点都大于该节点；


// 运用场景：
// 可以用在全文搜索一个内容时， 比如一个文章中你需要查找的内容出现在哪一行或者哪个位置，
//比如海量数据并发查询，  在数据压缩上有重要应用， 提高了传输的有效性。在处理大批量的动态的数据是比较有用。
//首创建节点
class CreatNode {
    constructor(key) {
        // 设置插入值
        this.key = key;
        // 左叉树
        this.left = null;
        // 右叉树
        this.right = null;
    }
}
//然后创建二叉树 (BST)）
class CreatBinaryTree {
    constructor() { // 设置根节点
        this.rootNode = null;
    }
    // 在排序二叉树中，插入元素首先要找插入位置，即新节点的父节点。
    //
    // 与查找元素类似从根节点开始找：
    //
    // 1）与当前节点相同，则已经存在了，不能插入；
    //
    // 2）如果小于当前节点，则到左子树中查找，如果左子树为空，则当前节点为要找到的父节点；
    //
    // 3）如果大于当前节点则到右子树中查找，如果右子树为空，则当前节点为要找的父节点。
    // 插入节点
    insert(node) {
        const newNode = new CreatNode(node);
        // 插入叶子节点
        const insertNode = (parentNode, newNode) => {
            // 新节点和老节点 如果新节点比老节点小  就把新节点放在左边
            if (newNode.key < parentNode.key) {
                // 判断如果左节点没有子节点
                if (parentNode.left === null) {
                    parentNode.left = newNode;
                } else {
                    // 如果有老节点有左子节点 就在左子节点的左边递归添加
                    insertNode(parentNode.left, newNode)
                }
            } else {
                // 如果新节点比老节点大  就把新节点放在在右边
                if (parentNode.right === null) {
                    parentNode.right = newNode;
                } else {
                    // 如果有老节点有右子节点 就在右子节点的右边递归添加
                    insertNode(parentNode.right, newNode)
                }
            }
        }
        // 判断根（父）节点是否为null
        if (this.rootNode == null) {
            // 新节点的值赋给父节点
            this.rootNode = newNode;
        } else {
            // 不为空时就往下插入数据节点
            // 插入节点要和父节点root对比  设置一个对比函数
            insertNode(this.rootNode, newNode);
        }
    }
     // 三种遍历  中序遍历 前序遍历  后序遍历
    //中序遍历  升序或降序
    inOrder() {
        let callbackArr = [];
        const inOrderNode = (node, callback) => {
            if (node !== null) {
                // 递归访问左子树一直访问到为空       然后返回到当前的父节点
                inOrderNode(node.left, callback);
                // 返回 访问当前父节点的key值添加到数组里
                callbackArr.push(callback(node.key));
                // 递归访问右子树一直访问到为空       然后返回到当前的父节点
                inOrderNode(node.right, callback);
            }
        };
        // 每个节点的回调函数
        // 先从父节点遍历查找子节点是否为null和每个节点的回调函数 对比
        inOrderNode(this.rootNode, (key) => {
            console.log(key)
            return key;
        });
        return callbackArr;
    }
    //前序遍历 作用当有个二叉树时重新复制一份二叉树
    preOrder() {
        let callbackArr = [];
        const preOrderNode = (node, callback) => {
            if (node !== null) {
                // 先访问当前节点输出当前节点然后再去访问左节点一直到null再去访问右节点。

                // 直接访问当前父节点的key值添加到数组里
                callbackArr.push(callback(node.key));
                // 然后递归查看左子节点有没有叶子节点
                preOrderNode(node.left, callback);
                // 然后递归查看右子节点有没有叶子节点
                preOrderNode(node.right, callback)
            }
        };
        preOrderNode(this.rootNode, (key) => {
            console.log(key)
            return key;
        });
        return callbackArr;
    }
    //后序遍历
    postOrder() {
        let callbackArr = [];
        const postOrderNode = (node, callback) => {
            if (node !== null) {
                // 优先输出左子树一直到最后到叶子节点，，然后寻找右子树 然后返回中间节点
                // 先访问左右子节点有没有叶子节点
                // 然后递归查看左子节点有没有叶子节点
                postOrderNode(node.left, callback);
                // 然后递归查看右子节点有没有叶子节点
                postOrderNode(node.right, callback);
                // 最后访问到没有左右子节点了添加进去
                callbackArr.push(callback(node.key))
            }
        };
        postOrderNode(this.rootNode, (key) => {
            return key;
        });
        return callbackArr;
    }
    // 1.查找
    // 1）首先与根节点比较，相同则找到；
    //
    // 2）如果小于根节点，则到左子树种递归查找；
    //
    // 3）如果大于根节点，则到右子树中递归查找；
    //
    // 这个步骤与在数组中进行二分查找是类似的。此外，在排序二叉树中查找最大值和最小值很简单。
    //查找最小值
    getMinNum(node) {
        const minNode = node => {
            //  从左子节点找最小值
            return node ? (node.left ? minNode(node.left) : node.key) : null
        };
        return minNode(node || this.rootNode)
    }
    //查找最大值
    getMaxNum(node) {
        const maxNode = node => {
            //  从右子节点找最大值
            return node ? (node.right ? maxNode(node.right) : node.key) : null
        };
        return maxNode(node || this.rootNode)
    }


    //查找特定值
    getFindNum(data) {
        const findNode = (node, data) => {
            if (node === null) return false; //如果根节点不存在就返回false
            // 要查找的值小于当前节点的值，用左子树继续查找
            if (data < node.key) {
                return findNode(node.left, data);
            } else if (data > node.key) {
                // 要查找的值大于当前节点的值，用右子树继续查找
                return findNode(node.right, data);
            } else {
                return true;
            }
        };
        return findNode(this.rootNode, data)
    }

    //
    // 从排序二叉树中删除一个节点，主要有三种情况：
    //
    // 1）节点为叶子节点: 直接删除
    //
    // 2）节点只有一个孩子节点：
    //
    // 删除当前节点，让其子节点与父节点建立链接

    //删除某节点值
    remove(data) {
        const removeNode = (node, data) => {
            if (node === null) return null; //如果不存在就返回null
            // 要查找的值小于当前节点的值，用左子树继续查找
            if (data < node.key) {
                node.left = removeNode(node.left, data);
                return node;
            } else if (data > node.key) {
                // 要查找的值大于当前节点的值，用右子树继续查找
                node.right = removeNode(node.right, data);
                return node;
            } else {
                if (node.left === null && node.right === null) return null;
                if (node.left === null) return node.right;
                if (node.right === null) return node.left;
                //在右子树中找到最小值节点
                var _node = this.getMinNum(node.right);
                // 将_node最小值节点的值更新为node最小值节点的值
                node.key = _node.key;
                // 因为最小值节点在右子树中 所以要从右子树中查找删除
                node.right = removeNode(node.right, node.key);
                // 然后返回节点
                return node;
            }
        };
        return removeNode(this.rootNode, data)
    }
}

// 实例化
const binaryTree = new CreatBinaryTree();
//

// // 一、 插入节点 这里单个 一个一个插入
// binaryTree.insert(16);
// binaryTree.insert(9);
// binaryTree.insert(15);
// binaryTree.insert(4);
// binaryTree.insert(16);
// binaryTree.insert(18);
// binaryTree.insert(14);
// binaryTree.insert(17);
// binaryTree.insert(11);
// binaryTree.insert(17);
// binaryTree.insert(24);
// binaryTree.insert(17);
// binaryTree.insert(28);
// // 二、 设置一个数组批量插入
var nodeList = [16,15, 4, 18, 14, 17, 24,17,28];
nodeList.forEach((key) => {
    binaryTree.insert(key);
});
console.log("tree", binaryTree); //得到二叉树结构
console.log(binaryTree.inOrder()); //中序排列   【4, 9, 11, 14, 15, 16, 16, 17, 17, 17, 18, 24, 28 ]
// console.log(binaryTree.preOrder()); //前序排列   [ 16, 9, 4, 15, 14, 11, 16, 18, 17, 17, 17, 24, 28 ]
// console.log(binaryTree.postOrder()); //后序排列   [ 4, 11, 14, 15, 9, 17, 17, 17, 28, 24, 18, 16, 16 ]
// console.log(binaryTree.getMinNum()); //查找最小值   4
// console.log(binaryTree.getMaxNum()); //查找最大值  28
// console.log(binaryTree.getFindNum(12)); //查找最大值   false
// console.log(binaryTree.getFindNum(28)); //查找特定值   true
// console.log(binaryTree.remove(4)); ////删除某值  节点    true

              </pre>
            </div>
            <div class="random-detail" id="ran5">
                <pre class="brush:javascript">
                    function BinaryTree() {
    var Node = function(key) {
        this.key = key;
        this.left = null;
        this.right = null;
    }
    // 根节点
    var root = null;

    // 插入root的子节点
    var insertNode = function(parentNode, newNode) {
        if (newNode.key < parentNode.key) {
            if (parentNode.left === null) {
                parentNode.left = newNode;
            } else {
                insertNode(parentNode.left, newNode)
            }
        } else {
            if (parentNode.right === null) {
                parentNode.right = newNode;
            } else {
                insertNode(parentNode.right, newNode)
            }
        }
    }
    // 先插入根节点
    this.insert = function(key) {
        var newNode = new Node(key);
        if (root == null) {
            root = newNode;
        } else {
            insertNode(root, newNode);
        }
    };
    // 前序遍历
    var inOrderTraverseNode = function(node, callback) {
        // 判断当前不为null的话就访问左右子节点树
        if (node !== null) {
            // 访问左子树
            inOrderTraverseNode(node.left, callback);
            // 访问当前节点的key值
            callback(node.key);
            // 访问右子树
            inOrderTraverseNode(node.right, callback)
        }
    }

    this.inOrderTraverse = function(callback) {
        // 先从根节点遍历和每个节点的回调函数
        inOrderTraverseNode(root, callback)
    }
    // 前序遍历
    var preOrderTraverseNode = function(node, callback) {
        // 判断当前不为null的话就访问左右子节点树
        if (node !== null) {
            // 访问当前节点的key值
            callback(node.key);
            // 访问左子树
            preOrderTraverseNode(node.left, callback);
            // 访问右子树
            preOrderTraverseNode(node.right, callback)


        }
    }
    this.preOrderTraverse = function(callback) {
        // 先从根节点遍历和每个节点的回调函数
        preOrderTraverseNode(root, callback)
    }
    // 后续遍历
    var postOrderTraverseNode = function(node, callback) {
        // 判断当前不为null的话就访问左右子节点树
        if (node !== null) {
            // 访问当前节点的key值
            callback(node.key);
            // 访问左子树
            postOrderTraverseNode(node.left, callback);
            // 访问右子树
            postOrderTraverseNode(node.right, callback)
        }
    }
    this.postOrderTraverse = function(callback) {
        // 先从根节点遍历和每个节点的回调函数
        postOrderTraverseNode(root, callback)
    }
    //查找最小值
    this.getMinNum = function(node) {
        const minNode = node => {
            // 如果定义左子节点小于右子节点， 那就从左子节点找最小值
            return node ? (node.left ? minNode(node.left) : node.key) : null
        };
        return minNode(node || root)
    }
    //查找最大值
    this.getMaxNum = function(node) {
        const maxNode = node => {
            // 如果定义左子节点小于右子节点， 那就从左子节点找最小值
            return node ? (node.right ? maxNode(node.right) : node.key) : null
        };
        return maxNode(node || root)
    }
    //查找特定值
    this.getFindNum = function(data) {
        const findNode = (node, data) => {
            if (node === null) return false;
            // 要查找的值小于当前节点的值，用左子树继续查找
            if (data < node.key) {
                return findNode(node.left, data);
            } else if (data > node.key) { // 要查找的值大于当前节点的值，用右子树继续查找
                return findNode(node.right, data);
            } else {
                return true;
            }
        };
        return findNode(root, data)
    }
    //删除某节点值
    this.remove=function(data) {
        const removeNode = (node, data) => {
            if (node === null) return null; //如果不存在就返回null
            // 要查找的值小于当前节点的值，用左子树继续查找
            if (data < node.key) {
                node.left = removeNode(node.left, data);
                return node;
            } else if (data > node.key) {
                // 要查找的值大于当前节点的值，用右子树继续查找
                node.right = removeNode(node.right, data);
                return node;
            } else {
                if (node.left === null && node.right === null) return null;
                if (node.left === null) return node.right;
                if (node.right === null) return node.left;
                //在右子树中找到最小值节点
                var _node = this.getMinNum(node.right);
                // 将_node最小值节点的值更新为node最小值节点的值
                node.key = _node.key;
                // 因为最小值节点在右子树中 所以要从右子树中查找删除
                node.right = removeNode(node.right, node.key);
                // 然后返回节点
                return node;
            }
        };
        return removeNode(root, data)
    }

}

// var nodes = [16, 9, 15, 4, 16, 18, 14, 17, 24, 17, 28];
// var binaryTree = new BinaryTree();
// nodes.forEach(function(key) {
//     binaryTree.insert(key);
// });
//
// console.log("tree", binaryTree) //得到二叉树结构
// console.log(binaryTree.inOrderTraverse(callback)) //中序排列   【4, 9, 11, 14, 15, 16, 16, 17, 17, 17, 18, 24, 28 ]
// console.log(binaryTree.preOrderTraverse(callback)) //前序排列   [ 16, 9, 4, 15, 14, 11, 16, 18, 17, 17, 17, 24, 28 ]
// console.log(binaryTree.postOrderTraverse(callback)) //后序排列   [ 4, 11, 14, 15, 9, 17, 17, 17, 28, 24, 18, 16, 16 ]
// console.log(binaryTree.getMinNum()) //查找最小值   4
// console.log(binaryTree.getMaxNum()) //查找最大值  28
// console.log(binaryTree.getFindNum(12)) //查找最大值   false
// console.log(binaryTree.getFindNum(28)) //删除某值  节点 28

                </pre>>
            </div>
        </div>

    </div>
</div>

<script>
    // @global xq 全局变量命名空间
    var xq = {};
    // 测试以上函数 方便演示代码， 添加代码高亮插件
    xq.t_array = [4, 2, 5, 5, 8, 12, 43, 7, 2];
    xq.unique_fns = {};
    xq.sort_fns = {};
    xq.random_fns = {};
    xq.sort_array = [5, 6, 3, 4, 9, 7, 8, 12, 10, 11, 2, 1];
    init();

    function init() {
        var unique_btn, sort_btn, twoTree, random_btn, unique_panel, sort_panel, unique_radios, sort_radios;
        unique_btn = document.getElementById('uniqueBtn');
        sort_btn = document.getElementById('sortBtn');
        random_btn = document.getElementById('randomBtn');
        twoTree = document.getElementById('twoTree');
        unique_btn.onclick = showUniquePanel;
        sort_btn.onclick = showSortPanel;
        random_btn.onclick = showRandomPanel;
        twoTree.onclick = showTwoTreePanel;
        // raido 事件处理
        unique_radios = document.getElementsByName('unique');
        sort_radios = document.getElementsByName('sort');
        random_radios = document.getElementsByName('random');
        // 初始化 数组函数
        initArrayFns();
        // 初始化 数组去重radio事件
        initRadios(unique_radios, 'un-detail');
        // 初始化 数组排序radio事件
        initRadios(sort_radios, 'sort-detail');
        // 初始化 随机数组radio事件
        initRadios(random_radios, 'random-detail');
        // 代码高亮显示
        // SyntaxHighlighter.config.clipboardSwf = 'http://static.oschina.net/js/syntax-highlighter-2.1.382/scripts/clipboard.swf';
        // SyntaxHighlighter.all();
        // 根据URL判断进入哪个Demo
        gotoDemo();
    }

    // 根据URL判断进入哪个Demo: array.html#t=unique&d=r1
    function gotoDemo() {
        var t_url, panel_type, panel_detail;
        // 根据URL现实对应内容
        t_url = window.location.hash.replace('#', '');
        t_url = !!t_url ? t_url.split('&') : '';
        if (t_url && t_url.length > 0) {
            panel_type = t_url[0].split('=')[1];
            panel_detail = t_url[1].split('=')[1];
            if (panel_type === 'sort') {
                // 显示数组排序 demo
                showSortPanel();
                // 触发对应radio
                triggerRadio('sort', panel_detail);
                // 默认去重radio触发
                triggerRadio('unique', 'r5');
                // 默认显示 获取N个值
                triggerRadio('random', 'ran1');
            } else if (panel_type === 'unique') {
                // 显示数组去重 demo
                showUniquePanel();
                // 触发对应radio
                triggerRadio('unique', panel_detail);
                // 默认排序radio触发
                triggerRadio('sort', 's6');
                // 默认显示 获取N个值
                triggerRadio('random', 'ran1');
            } else if (panel_type === 'random') {
                // 显示随机数组 demo
                showRandomPanel();
                // 触发对应radio
                triggerRadio('random', panel_detail);
                // 默认去重radio触发
                triggerRadio('unique', 'r5');
                // 默认排序radio触发
                triggerRadio('sort', 's6');
            }
        } else {
            // 默认显示数组去重 demo
            showUniquePanel();
            // 默认显示优化遍历数组法
            showDetail('r5', 'un-detail');
            // 默认显示 快速排序
            showDetail('s6', 'sort-detail');
            // 默认显示 获取N个值
            showDetail('ran1', 'random-detail');
        }
    }

    // 初始化 算法函数
    function initArrayFns() {
        // 初始化去重函数
        xq.unique_fns['r1'] = unique1;
        xq.unique_fns['r2'] = unique2;
        xq.unique_fns['r3'] = unique3;
        xq.unique_fns['r4'] = unique4;
        xq.unique_fns['r5'] = unique5;
        // 初始化排序函数
        xq.sort_fns['s1'] = sort1;
        xq.sort_fns['s2'] = sort2;
        xq.sort_fns['s3'] = sort3;
        xq.sort_fns['s4'] = sort4;
        xq.sort_fns['s5'] = sort5;
        xq.sort_fns['s6'] = sort6;
        xq.sort_fns['s7'] = sort7;
        xq.sort_fns['s8'] = sort8;
        xq.sort_fns['s9'] = sort9;
        // 初始化随机函数
        xq.random_fns['ran1'] = ran1;
        xq.random_fns['ran2'] = ran2;
        xq.random_fns['ran3'] = ran3;
    }

    function showUniquePanel() {
        showPanel('uniquePanel');
    }

    function showSortPanel() {
        showPanel('sortPanel');
    }

    function showRandomPanel() {
        showPanel('randomPanel');
    }

    function showTwoTreePanel() {
        showPanel('twoTreePanel');
    }

    function triggerRadio(type, r_id) {
        var radios, i, len, radio;
        // 获得radios列表
        radios = document.getElementsByName(type);
        for (i = 0, len = radios.length; i < len; i++) {
            radio = radios[i];
            if (radio.getAttribute('data-id') === r_id) {
                radio.click();
                break;
            }
        }
    }

    function hideAllPanel() {
        var panel_list, i, len, p_item;
        panel_list = document.getElementsByClassName('panel');
        for (i = 0, len = panel_list.length; i < len; i++) {
            p_item = panel_list[i];
            p_item.style.display = 'none';
        }
    }

    function showPanel(p_id) {
        var p_item;
        hideAllPanel();
        p_item = document.getElementById(p_id);
        p_item.style.display = 'block';
    }

    // 初始化 radio按钮事件
    function initRadios(btn_list, p_class) {
        var i, len, btn, b_id;
        for (i = 0, len = btn_list.length; i < len; i++) {
            btn = btn_list[i];
            btn.onclick = function () {
                var b_id = this.getAttribute('data-id');
                showDetail(b_id, p_class);
            }
        }
    }

    // 隐藏指定类型的所有详情面板
    function hideAllDetail(detail_list) {
        var i, len, detail;
        if (!detail_list || detail_list.length == 0) {
            return false;
        }
        for (i = 0, len = detail_list.length; i < len; i++) {
            detail = detail_list[i];
            detail.style.display = 'none';
        }
    }

    // 显示某一详情面板
    function showDetail(u_id, p_class) {
        var detail_list, show_detail, result, result_panel;
        if (!u_id) {
            return false;
        }
        detail_list = document.getElementsByClassName(p_class);
        show_detail = document.getElementById(u_id);
        hideAllDetail(detail_list);
        show_detail.style.display = 'block';
        if (p_class === 'un-detail' && (typeof xq.unique_fns[u_id]) === 'function') {
            // 执行对应函数
            result = xq.unique_fns[u_id](xq.t_array);
            // 结果显示在对应面板中
            result_panel = document.getElementById(u_id + '-res');
            result_panel.innerHTML = '';
            result_panel.appendChild(document.createTextNode(result));
        } else if (p_class === 'sort-detail' && (typeof xq.sort_fns[u_id]) === 'function') {
            // 执行对应函数
            result = xq.sort_fns[u_id](xq.sort_array);
            // 结果显示在对应面板中
            result_panel = document.getElementById(u_id + '-res');
            result_panel.innerHTML = '';
            result_panel.appendChild(document.createTextNode(result));
        } else if (p_class === 'random-detail' && (typeof xq.random_fns[u_id]) === 'function') {
            // 执行对应函数
            result = xq.random_fns[u_id](xq.sort_array);
            // 结果显示在对应面板中
            result_panel = document.getElementById(u_id + '-res');
            result_panel.innerHTML = '';
            result_panel.appendChild(document.createTextNode(result));
        }
    }

    // 最简单数组去重法
    function unique1(array) {
        var n = []; //一个新的临时数组
        //遍历当前数组
        for (var i = 0; i < array.length; i++) {
            //如果当前数组的第i已经保存进了临时数组，那么跳过，
            //否则把当前项push到临时数组里面
            if (n.indexOf(array[i]) == -1) n.push(array[i]);
        }
        return n;
    }

    // 速度最快， 占空间最多（空间换时间）
    function unique2(array) {
        var n = {},
            r = [],
            len = array.length,
            val, type;
        for (var i = 0; i < array.length; i++) {
            val = array[i];
            type = typeof val;
            if (!n[val]) {
                n[val] = [type];
                r.push(val);
            } else if (n[val].indexOf(type) < 0) {
                n[val].push(type);
                r.push(val);
            }
        }
        return r;
    }

    function unique3(array) {
        var n = [array[0]]; //结果数组
        //从第二项开始遍历
        for (var i = 1; i < array.length; i++) {
            //如果当前数组的第i项在当前数组中第一次出现的位置不是i，
            //那么表示第i项是重复的，忽略掉。否则存入结果数组
            if (array.indexOf(array[i]) == i) n.push(array[i]);
        }
        return n;
    }

    // 将相同的值相邻，然后去除
    function unique4(array) {
        array.sort();
        var re = [array[0]];
        for (var i = 1; i < array.length; i++) {
            if (array[i] !== re[re.length - 1]) {
                re.push(array[i]);
            }
        }
        return re;
    }

    // 思路：获取没重复的最右一值放入新数组
    function unique5(array) {
        var r = [];
        for (var i = 0, l = array.length; i < l; i++) {
            for (var j = i + 1; j < l; j++)
                if (array[i] === array[j]) j = ++i;
            r.push(array[i]);
        }
        return r;
    }

    // 插入排序 从下标1开始每增1项排序一次，越往后遍历次数越多
    function sort1(array) {
        var len = array.length,
            i, j, tmp, result;
        // 赋予数组副本
        result = array.slice(0);
        for (i = 1; i < len; i++) {
            tmp = result[i];
            j = i - 1;
            while (j >= 0 && tmp < result[j]) {
                result[j + 1] = result[j];
                j--;
            }
            result[j + 1] = tmp;
        }
        return result;
    }

    // 先在有序区通过二分查找的方法找到移动元素的起始位置，然后通过这个起始位置将后面所有的元素后移
    // 关于二分查找排序，该贴子的图比较易懂http://www.cnblogs.com/liuling/p/2013-7-24-01.html
    function sort2(array) {
        var len = array.length,
            i, j, tmp, low, high, mid, result;
        // 赋予数组副本
        result = array.slice(0);
        for (i = 1; i < len; i++) {
            tmp = result[i];
            low = 0;
            high = i - 1;
            while (low <= high) {
                mid = parseInt((low + high) / 2, 10);
                if (tmp < result[mid]) high = mid - 1;
                else low = mid + 1;
            }
            for (j = i - 1; j >= high + 1; j--) {
                result[j + 1] = result[j];
            }
            result[j + 1] = tmp;
        }
        return result;
    }

    // 希尔排序：
    function sort3(array) {
        var len = array.length,
            gap = parseInt(len / 2),
            i, j, tmp, result;
        // 复制数组
        result = array.slice(0);
        while (gap > 0) {
            for (i = gap; i < len; i++) {
                tmp = result[i];
                j = i - gap;
                while (j >= 0 && tmp < result[j]) {
                    result[j + gap] = result[j];
                    j = j - gap;
                }
                result[j + gap] = tmp;
            }
            gap = parseInt(gap / 2);
        }
        return result;
    }

    // 冒泡排序 每次将最小元素推至最前
    function sort4(array) {
        var len = array.length,
            i, j, tmp, result;
        result = array.slice(0);
        for (i = 0; i < len; i++) {
            for (j = len - 1; j > i; j--) {
                if (result[j] < result[j - 1]) {
                    tmp = result[j - 1];
                    result[j - 1] = result[j];
                    result[j] = tmp;
                }
            }
        }
        return result;
    }

    // 如果在某次的排序中没有出现交换的情况，那么说明在无序的元素现在已经是有序了，就可以直接返回了。
    function sort5(array) {
        var len = array.length,
            i, j, tmp, exchange, result;
        result = array.slice(0);
        for (i = 0; i < len; i++) {
            exchange = 0;
            for (j = len - 1; j > i; j--) {
                if (result[j] < result[j - 1]) {
                    tmp = result[j];
                    result[j] = result[j - 1];
                    result[j - 1] = tmp;
                    exchange = 1;
                }
            }
            if (!exchange) return result;
        }
        return result;
    }

    //（1）在数据集之中，选择一个元素作为"基准"（pivot）。
    //（2）所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素，都移到"基准"的右边。
    //（3）对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
    function sort6(array) {
        var tmp_array = array.slice(0),
            result, quickSort;
        quickSort = function (arr) {
            if (arr.length <= 1) {
                return arr;
            }
            var pivotIndex = Math.floor(arr.length / 2);
            var pivot = arr.splice(pivotIndex, 1)[0];
            var left = [];
            var right = [];
            for (var i = 0; i < arr.length; i++) {
                if (arr[i] < pivot) {
                    left.push(arr[i]);
                } else {
                    right.push(arr[i]);
                }
            }
            return quickSort(left).concat([pivot], quickSort(right));
        };
        result = quickSort(tmp_array);
        return result;
    }

    // 在无序区中选出最小的元素，然后将它和无序区的第一个元素交换位置。
    // 冒泡排序的衍生版本
    function sort7(array) {
        var len = array.length,
            i, j, k, tmp, result;
        result = array.slice(0);
        for (i = 0; i < len; i++) {
            k = i;
            for (j = i + 1; j < len; j++) {
                if (result[j] < result[k]) k = j;
            }
            if (k != i) {
                tmp = result[k];
                result[k] = result[i];
                result[i] = tmp;
            }
        }
        return result;
    }

    // 1) 初始堆：将原始数组调整成大根堆的方法——筛选算法:子节点都比父节点小
    // 2) 堆排序： 每次将堆顶元素与数组最后面的且没有被置换的元素互换。
    // 参考代码： http://bubkoo.com/2014/01/14/sort-algorithm/heap-sort/
    function sort8(array) {
        var result = array.slice(0);

        function swap(array, i, j) {
            var temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

        function maxHeapify(array, index, heapSize) {
            var iMax,
                iLeft,
                iRight;
            while (true) {
                iMax = index;
                iLeft = 2 * index + 1;
                iRight = 2 * (index + 1);
                if (iLeft < heapSize && array[index] < array[iLeft]) {
                    iMax = iLeft;
                }
                if (iRight < heapSize && array[iMax] < array[iRight]) {
                    iMax = iRight;
                }
                if (iMax != index) {
                    swap(array, iMax, index);
                    index = iMax;
                } else {
                    break;
                }
            }
        }

        function buildMaxHeap(array) {
            var i,
                iParent = Math.floor(array.length / 2) - 1;
            for (i = iParent; i >= 0; i--) {
                maxHeapify(array, i, array.length);
            }
        }

        function sort(array) {
            buildMaxHeap(array);
            for (var i = array.length - 1; i > 0; i--) {
                swap(array, 0, i);
                maxHeapify(array, 0, i);
            }
            return array;
        }

        return sort(result);
    }

    // 合并排序：将无序的数组 拆成N部分进行有序处理，然后合并；
    // 参考代码： https://gist.github.com/paullewis/1982121
    function sort9(array) {
        var result = array.slice(0);

        // 递归调用合并函数
        function sort(array) {
            var length = array.length,
                mid = Math.floor(length * 0.5),
                left = array.slice(0, mid),
                right = array.slice(mid, length);
            if (length === 1) {
                return array;
            }
            return merge(sort(left), sort(right));
        }

        // 合并 两有序的数组
        function merge(left, right) {
            var result = [];
            while (left.length || right.length) {
                if (left.length && right.length) {
                    if (left[0] < right[0]) {
                        result.push(left.shift());
                    } else {
                        result.push(right.shift());
                    }
                } else if (left.length) {
                    result.push(left.shift());
                } else {
                    result.push(right.shift());
                }
            }
            return result;
        }

        return sort(result);
    }

    // 随机从数组中获取 N个不重复的值, 默认从数组取一个值
    function ran1(array, n) {
        var _result = [],
            _index = 0,
            _arrayTemp;
        // 防止原数组被改变
        _arrayTemp = array.slice(0);
        if (array == null || array.length == 0 || array.length < n) {
            return _result;
        }
        // 随机获取一个值
        if (n == null) {
            _index = Math.floor(Math.random() * array.length);
            _result.push(array[_index]);
        } else {
            // 随机获取N个值
            for (var i = 0; i < n; i++) {
                _index = Math.floor(Math.random() * _arrayTemp.length);
                _result.push(_arrayTemp[_index]);
                // 删除该元素
                _arrayTemp.splice(_index, 1);
            }
        }
        return _result;
    }

    // 随机打乱数组，使数组内元素与原来位置完全不同
    function ran2(array) {
        var array_tmp = [],
            i, j, len, new_a = [],
            a_obj;

        // 添加数组原位置标志位
        for (i = 0, len = array.length; i < len; i++) {
            a_obj = {
                'key': i,
                'val': array[i]
            };
            array_tmp.push(a_obj);
        }
        for (i = 0, len = array.length; i < len; i++) {
            j = ranCount(array_tmp.length);
            // 如下标位置与原值重复，重新随机
            while (i === array_tmp[j].key) {
                j = ranCount(array_tmp.length);
            }
            new_a.push(array_tmp[j].val);
            // 删除数组
            array_tmp.splice(j, 1);
        }

        // 获得给定数字的随机数, 出错返回-1
        function ranCount(n) {
            var result = parseInt(n, 10);
            if (isNaN(result)) {
                result = -1;
            }
            result = Math.floor(Math.random() * result)
            return result;
        }

        return new_a;
    }

    // 从指定范围内，随机获取N个值的数组
    function ran3() {
        var result = [],
            SCOPE_NO = 100,
            COUNT = 10;
        result = getRandomNo(SCOPE_NO, COUNT);

        function getRandomNo(scope_no, count) {
            var i, s_n, ran_n, _result = [];

            s_n = parseInt(scope_no, 10);
            for (i = 0; i < count; i++) {
                ran_n = Math.floor(Math.random() * s_n);
                _result.push(ran_n);
            }
            return _result;
        }

        return result;
    }
</script>
<script src="./MyFrame.js"></script>
<script>
    console.log(FF.isNumber(12))

</script>
</body>
<style>
    pre {outline: 1px solid #ccc; }

</style>

</html>
